#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//初始化堆
void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->capacity = 0;
	php->size = 0;

}
//交换函数
void Swap(HeapDataType* x1, HeapDataType* x2)
{
	HeapDataType tmp;
	tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;

}
//向上调整函数
void AdjustUp(HeapDataType* a, int child)
{
	//初始化父亲下标
	int parent = (child - 1) / 2;
	//child>0 代表未比对完
	while (child > 0)
	{
		//孩子比父亲小，则交换
		//然后更新孩子和父亲的下标
		if (a[child] < a[parent])
		{
			Swap(&(a[child]), &(a[parent]));
			child = parent;
			parent = (child - 1) / 2;
		}
		//孩子比父亲大，根据堆的特性，则不用继续对比		
		else
		{
			break;
		}
	}
}
//向下调整函数
void AdjustDown(HeapDataType* a, int n, int parent)
{
	//根据传过来的parent初始化child（左孩子公式）
	//假设左孩子为最小的孩子
	int child = parent * 2 + 1;
	//
	while (child < n)
	{
		//假设左孩子为左右孩子较小的，可能会出错
		//&&左确认了有有孩子，&&右边确认了 右孩子更小
		if (child + 1 < n && a[child + 1] < a[child])
		{
			//更改较小孩子的下标
			child = child + 1;
		}
		//孩子比父亲小，需要交换
		//再更新孩子和父亲的下标
		if (a[child] < a[parent])
		{
			Swap(&(a[parent]), &(a[child]));
			parent = child;
			child = parent * 2 + 1;
		}
		//孩子不比父亲小，根据小堆特性，不用继续比较了。
		else
		{
			break;
		}
	}
}
//堆的插入
void HeapPush(HP* php, HeapDataType x)
{
	//断言
	assert(php);
	//判断是否为满
	if (php->capacity == php->size)
	{   //根据满的情况（二者都为0，还是装满了）来确定新的capacity的值
		int NewCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		//开辟一个大小为新的capacity的空间 给 tmp
		HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		//通过中转量把 a和 capacity 都更新
		php->a = tmp;
		php->capacity = NewCapacity;
	}
	//插入先赋值然后size+1
	php->a[php->size] = x;
	php->size++;

	//向上调整函数
	AdjustUp(php->a, php->size - 1);
}

//堆的删除（删除根节点）
void HeapPop(HP* php)
{
	//断言
	assert(php);

	//断言确保有元素
	assert(php->size > 0);

	//交换
	Swap(&(php->a[0]), &(php->a[php->size - 1]));
	//抹去最后一个元素
	php->size--;
	//向下调整
	AdjustDown(php->a, php->size, 0);

}
//取堆顶数据
HeapDataType HeapTop(HP* php)
{
	assert(php);
	//断言确保有元素
	assert(php->size > 0);
	return("%d", php->a[0]);

}
//堆的打印
void HeapPrint(HP* php)
{
	assert(php);
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
//堆的数据个数
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
//堆的销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}